package Demo2_7;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-07
 * Time:17:04
 */
import java.util.Scanner;

// 定义二叉树节点类
class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;

    TreeNode(char val) {
        this.val = val;
    }
}

public class BinaryTreeTraversal {
    // 全局变量，用于记录当前处理的字符索引
    private static int index = 0;

    // 根据先序遍历字符串构建二叉树
    public static TreeNode buildTree(String preorder) {
        if (index >= preorder.length()) {
            return null;
        }
        char ch = preorder.charAt(index++);
        if (ch == '#') {
            return null;
        }
        TreeNode node = new TreeNode(ch);
        node.left = buildTree(preorder);
        node.right = buildTree(preorder);
        return node;
    }

    // 中序遍历二叉树
    public static void inorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left);
        System.out.print(root.val + " ");
        inorderTraversal(root.right);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入先序遍历字符串: ");
        String preorder = scanner.nextLine();
        scanner.close();

        // 构建二叉树
        TreeNode root = buildTree(preorder);

        // 中序遍历并输出结果
        System.out.print("中序遍历结果: ");
        inorderTraversal(root);
    }
}